package my;

import utils.Tools;

/**
 * <p>
 * 算法初识
 * </p>
 *
 * @author AJun
 * @since 2020/8/10
 */
public class Main01 {

    public static void main(String[] args) {
        Tools.calcTime("fib", () -> Tools.println(fib(40))); // 秒算: 0.0秒

        Tools.calcTime("fibRecursion", () -> Tools.println(fibRecursion(40))); // 效率低: 1.522秒
    }

    /**
     * 递归求第 n 个斐波那契数: fibonacci number  0  1  1  2  3  5  8  13 ...
     * 递归的话有效率问题，传入数字很大会很慢
     *
     * @param n 第几个
     * @return 斐波那契数
     */
    public static int fibRecursion(int n) {
        if (n <= 1) return n;
        return fibRecursion(n - 1) + fibRecursion(n - 2);
    }

    /**
     * 求第 n 个斐波那契数: fibonacci number  0  1  1  2  3  5  8  13 ...
     *
     * @param n 第几个
     * @return 斐波那契数
     */
    public static int fib(int n) {
        if (n <= 1) return n;

        int first = 0;
        int second = 1;
        for (int i = 0; i < n - 1; i++) {
            int sum = first + second;
            first = second;
            second = sum;
        }
        return second;
    }

    /**
     * 记忆化自底向上的方法
     * 时间复杂度：O(N)。
     * 空间复杂度：O(N)，使用了空间大小为 N 的数组。
     */
    public int fib1(int N) {
        if (N <= 1) {
            return N;
        }
        return memoize(N);
    }

    public int memoize(int N) {
        int[] cache = new int[N + 1];
        cache[1] = 1;

        for (int i = 2; i <= N; i++) {
            cache[i] = cache[i - 1] + cache[i - 2];
        }
        return cache[N];
    }

    /**
     * 自底向上进行迭代
     * 时间复杂度：O(N)。
     * 空间复杂度：O(1)，仅仅使用了 current，prev1，prev2。
     */
    public int fib2(int N) {
        if (N <= 1) {
            return N;
        }
        if (N == 2) {
            return 1;
        }

        int current = 0;
        int prev1 = 1;
        int prev2 = 1;

        for (int i = 3; i <= N; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return current;
    }

    /**
     * 矩阵求幂
     * 时间复杂度：O(logN)。
     * 空间复杂度：O(logN)，matrixPower 函数递归时堆栈使用的空间。
     */
    int fib3(int N) {
        if (N <= 1) {
            return N;
        }
        int[][] A = new int[][]{{1, 1}, {1, 0}};
        matrixPower(A, N - 1);

        return A[0][0];
    }

    void matrixPower(int[][] A, int N) {
        if (N <= 1) {
            return;
        }
        matrixPower(A, N / 2);
        multiply(A, A);

        int[][] B = new int[][]{{1, 1}, {1, 0}};
        if (N % 2 != 0) {
            multiply(A, B);
        }
    }

    void multiply(int[][] A, int[][] B) {
        int x = A[0][0] * B[0][0] + A[0][1] * B[1][0];
        int y = A[0][0] * B[0][1] + A[0][1] * B[1][1];
        int z = A[1][0] * B[0][0] + A[1][1] * B[1][0];
        int w = A[1][0] * B[0][1] + A[1][1] * B[1][1];

        A[0][0] = x;
        A[0][1] = y;
        A[1][0] = z;
        A[1][1] = w;
    }

    /**
     * 黄金分割比公式法
     * 时间复杂度：O(1)。常数的时间复杂度，因为我们是基于 Binet 公式进行计算，没有使用循环或递归。
     * 空间复杂度：O(1)，存储黄金分割率所使用的空间。
     */
    public int fib4(int N) {
        double goldenRatio = (1 + Math.sqrt(5)) / 2;
        return (int) Math.round(Math.pow(goldenRatio, N) / Math.sqrt(5));
    }


    /* 时间复杂度估算 */

    // 14 >> O(1)
    public static void test1(int n) {
        // 1
        if (n > 10)
            System.out.println("n > 10");
        else if ((n > 5) && (n < 10))
            System.out.println("10 > n > 5");
        else
            System.out.println("n <= 5");

        // 1 + 4 + 4 + 4
        for (int i = 0; i < 4; i++) {
            System.out.println("test");
        }
    }

    // 3n + 1 >> O(n)
    public static void test2(int n) {
        // 1 + n + n + n = 1 + 3n
        for (int i = 0; i < n; i++) {
            System.out.println("test");
        }
    }

    // 1 + 3n + 3n^2 >> O(n^2)
    public static void test3(int n) {
        // 1 + 2n + n * (1 + 3n) = 1 + 2n + n + 3n^2 = 1 + 3n + 3n^2
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n; k++) {
                System.out.println("test");
            }
        }
    }

    // 48n >> O(n)
    public static void test4(int n) {
        // 1 + 2n + n * (1 + 15 * 3) = 1 + 2n + 46n = 1 + 48n
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < 15; k++) {
                System.out.println("test");
            }
        }
    }

    // log2(n) >> O(log n)
    public static void test5(int n) {
        // n 能被除几次，那么就是几次
        // log2(n)
        while ((n = n / 2) > 0)
            System.out.println("test");
    }

    // log5(n) >> O(log n)
    public static void test6(int n) {
        // log5(n)
        while ((n = n / 5) > 0)
            System.out.println("test");
    }

    // 1 + 2 * log2(n) + (log2(n) * (3n + 1)) = 1 + 3log2(n) + 3nlog2(n) >> O(log n + nlog n)
    // O(log n + nlog n) >> nlog n
    public static void test7(int n) {
        // i += i 等价于 i = i + i 等价于 i * 2，所以是 i 能被乘几次，那么就是几次，也就是 n 能被 2 除几次就是几次
        // 1 + 2 * log2(n)
        for (int i = 1; i < n; i += i) {
            // log2(n) * (3n + 1)
            for (int k = 0; k < n; k++) {
                System.out.println("test");
            }
        }
    }

    /* 空间复杂度估算 */

    // O(1): 只用了一个 i 变量，算作 O(1)
    public static void test8(int n) {
        if (n > 10)
            System.out.println("n > 10");
        else if ((n > 5) && (n < 10))
            System.out.println("10 > n > 5");
        else
            System.out.println("n <= 5");

        for (int i = 0; i < 4; i++) {
            System.out.println("test");
        }
    }

    // o(n): 常数项不算，有一个数组，长度为 n，所以算作 O(n)
    public static void test9(int n) {
        int a = 10;
        int b = 20;
        int c = a + b;

        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i] + c);
        }
    }

    /* 多个数据规模 */

    // O(n + k)
    public static void test10(int n, int k) {
        for (int i = 0; i < n; i++) {
            System.out.println("test");
        }

        for (int i = 0; i < k; i++) {
            System.out.println("test");
        }
    }

}
